package com.example.myletcodelearing.one

import java.util.*


/**
 * @author tgw
 * @date 2022/11/7
 *      * 有向无环图的拓扑排序算法
 *
 * 参考：
 * https://blog.csdn.net/wat1r/article/details/119485748
 */

fun main(args: Array<String>) {
    val g = Solution26.Graph(6);
    //0 1 4 3 2 5
//    g.addEdge(2,5, );
//    g.addEdge(0,5, );
//    g.addEdge(0,4,);
//    g.addEdge(1,4, );
//    g.addEdge(3,2, );
//    g.addEdge(1,3, );
    //4 5 2 0 3 1
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
    val indexList = g.topologicalSort();

    for (i in indexList) {
        println("TAGtgwonClick: " + i);
    }

    val g2 = Solution26.Graph2(6);
    g2.addEdge(5, 2);
    g2.addEdge(5, 0);
    g2.addEdge(4, 0);
    g2.addEdge(4, 1);
    g2.addEdge(2, 3);
    g2.addEdge(3, 1);
    val indexList2 = g2.topologicalSort();


}

private class Solution26 {


    /**
     * 有向无环图的拓扑排序算法
     *
     * 参考：
     * https://blog.csdn.net/wat1r/article/details/119485748
     */
    internal class Graph(  //顶点数
        private val mVerticeCount: Int
    ) {
        //邻接表
        private val mAdj: Array<MutableList<Int>?> = arrayOfNulls<MutableList<Int>>(mVerticeCount)

        init {

            for (i in 0 until mVerticeCount) {
                mAdj[i] = ArrayList<Int>()
            }
        }

        /**
         * 添加边
         *
         * @param u from
         * @param v to
         */
        fun addEdge(u: Int, v: Int) {
            mAdj[u]?.add(v)
        }

        /**
         * 拓扑排序
         */
        fun topologicalSort(): Vector<Int> {
            val indegree = IntArray(mVerticeCount)
            for (i in 0 until mVerticeCount) { //初始化所有点的入度数量
                val temp = mAdj[i] as ArrayList<Int>
                for (node in temp) {
                    indegree[node]++
                }
            }
            val queue: Queue<Int> = LinkedList()
            for (i in 0 until mVerticeCount) { //找出所有入度为0的点
                if (indegree[i] == 0) {
                    queue.add(i)
                }
            }
            var cnt = 0
            val topOrder = Vector<Int>()
            while (!queue.isEmpty()) {
                val u = queue.poll()
                topOrder.add(u)
                for (node in mAdj[u]!!) { //找到该点（入度为0）的所有邻接点
                    if (--indegree[node] == 0) { //把这个点的入度减一，如果入度变成了0，那么添加到入度0的队列里
                        queue.add(node)
                    }
                }
                cnt++
            }
            check(cnt == mVerticeCount) {  //检查是否有环，理论上拿出来的点的次数和点的数量应该一致，如果不一致，说明有环
                "Exists a cycle in the graph"
            }
            return topOrder
        }
    }


    internal class Graph2(private val V: Int) {
        private val adj: MutableList<MutableList<Int>>

        //初始化构建图
        init {
            adj = ArrayList()
            for (i in 0 until V) {
                adj.add(ArrayList())
            }
        }

        //有向图
        fun addEdge(u: Int, v: Int) {
            adj[u].add(v)
        }

        fun topologicalSortUtil(u: Int, vis: BooleanArray, stk: Stack<Int>) {
            vis[u] = true //标记当前节点被访问过
            for (v in adj[u]) {
                if (!vis[v]) topologicalSortUtil(v, vis, stk)
            }
            stk.push(u) //加入当前节点
        }

        fun topologicalSort() {
            val stk: Stack<Int> = Stack()
            val vis = BooleanArray(V)
            for (u in 0 until V) { //依次遍历
                if (!vis[u]) topologicalSortUtil(u, vis, stk)
            }
            while (!stk.isEmpty()) {
                println("------:${stk.pop()} ")
            }
        }

    }


}
